package com.wf.javase;

import java.util.Arrays;

/**
 * @author mpk
 * @since 2024/6/22 15:01:19
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {12, 34, 65, 7, 83, 34, 6, 7, 8, 4, 3, 2};

        int[] ints = heapSortMethod(arr);

        System.out.println(Arrays.toString(ints));

        System.out.println(Math.floor(-4.6));

    }


    /**
     * @param arr 要排序的数组
     * @return 排序好的数组
     */
    private static int[] heapSortMethod(int[] arr) {

        //从最后一个非叶子节点开始排序
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapS(arr, arr.length, i);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            //交换最后一个节点与根节点
            swap(arr, 0, i);
            //组件大根堆
            heapS(arr, i, 0);
        }

        return arr;

    }

    /**
     * @param arr 要组成顶堆的数组
     * @param n   要组堆的元素个数
     * @param i   组堆的下标
     */

    private static void heapS(int[] arr, int n, int i) {

        //假设当前节点为最大节点
        int largest = i;
        //左子节点
        int leftChildren = 2 * i + 1;
        //右子节点
        int rightChildren = 2 * i + 2;

        //如果左节点大 最大节点=左节点
        if (leftChildren < n && arr[largest] < arr[leftChildren]) {
            largest = leftChildren;
        }
        //如果右节点大 最大节点=右节点
        if (rightChildren < n && arr[largest] < arr[rightChildren]) {
            largest = rightChildren;
        }

        //若发生交换 交换 递归
        if (largest != i) {
            swap(arr, largest, i);
            heapS(arr, n, largest);
        }


    }

    private static void swap(int[] arr, int a, int b) {

        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;

    }

}
